//+------------------------------------------------------------------+
//|                                                   LinkedList.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic/Interfaces/ICollection.h>   // 继承集合接口 ICollection<T>，获取基础集合能力
#include <Generic/Internal/EqualFunction.h>   // 内部相等性判断工具（处理元素相等逻辑）

//+------------------------------------------------------------------+
//| CLinkedListNode<T> 类：双向链表的节点类                          |
//| 核心定位：封装链表中的单个节点，存储元素值及前后节点指针          |
//| 用途：作为 CLinkedList<T> 的最小存储单元，实现节点间的双向关联    |
//+------------------------------------------------------------------+
template<typename T>
class CLinkedListNode
  {
protected:
   CLinkedList<T>*   m_list;         // 节点所属的链表（用于验证节点有效性）
   CLinkedListNode<T>* m_next;       // 指向后一个节点的指针（双向链表核心）
   CLinkedListNode<T>* m_prev;       // 指向前一个节点的指针（双向链表核心）
   T                 m_item;         // 节点存储的元素值

public:
   /**
    * @brief 带值构造函数：创建节点并初始化元素值，暂不关联链表
    * @param value [in] 节点存储的元素值
    */
                     CLinkedListNode(T value) : m_item(value) { }

   /**
    * @brief 带链表+值构造函数：创建节点并关联到指定链表，初始化元素值
    * @param list [in] 节点所属的链表（CLinkedList<T> 实例）
    * @param value [in] 节点存储的元素值
    */
                     CLinkedListNode(CLinkedList<T>* list, T value) : m_list(list), m_item(value) { }

   /**
    * @brief 析构函数：清理节点资源
    * @note 仅释放节点自身，不主动删除前后节点（由链表统一管理节点生命周期）
    */
                    ~CLinkedListNode(void) { }

   //----------------------------------------------------------------
   // 节点属性访问接口
   //----------------------------------------------------------------
   /**
    * @brief 获取节点所属的链表
    * @return CLinkedList<T>* - 所属链表实例（NULL 表示节点未关联链表）
    */
   CLinkedList<T>*   List(void) { return(m_list); }

   /**
    * @brief 设置节点所属的链表
    * @param value [in] 目标链表实例（CLinkedList<T> 指针）
    */
   void              List(CLinkedList<T>* value) { m_list = value; }

   /**
    * @brief 获取当前节点的后一个节点
    * @return CLinkedListNode<T>* - 后一个节点指针（循环链表中，尾节点的 next 指向头节点）
    */
   CLinkedListNode<T>* Next(void) { return(m_next); }

   /**
    * @brief 设置当前节点的后一个节点
    * @param value [in] 目标后节点指针（需为同一链表中的节点）
    */
   void              Next(CLinkedListNode<T>* value) { m_next = value; }

   /**
    * @brief 获取当前节点的前一个节点
    * @return CLinkedListNode<T>* - 前一个节点指针（循环链表中，头节点的 prev 指向尾节点）
    */
   CLinkedListNode<T>* Previous(void) { return(m_prev); }

   /**
    * @brief 设置当前节点的前一个节点
    * @param value [in] 目标前节点指针（需为同一链表中的节点）
    */
   void              Previous(CLinkedListNode<T>* value) { m_prev = value; }

   /**
    * @brief 获取节点存储的元素值
    * @return T - 元素值（类型与链表泛型参数 T 一致）
    */
   T                 Value(void) { return(m_item); }

   /**
    * @brief 修改节点存储的元素值
    * @param value [in] 新的元素值
    */
   void              Value(T value) { m_item = value; }
  };

//+------------------------------------------------------------------+
//| CLinkedList<T> 类：双向循环链表实现类                            |
//| 核心定位：实现 ICollection<T> 接口，基于双向循环链表存储元素，    |
//|           支持高效的节点插入/删除（尤其在链表头部/尾部/指定节点附近） |
//| 核心特性：                                                      |
//|  1. 双向循环：头节点的 prev 指向尾节点，尾节点的 next 指向头节点；  |
//|  2. 节点级操作：支持在指定节点前后插入/删除，无需移动大量元素；    |
//|  3. 动态内存：节点按需创建/释放，内存利用率高（无数组扩容浪费）；   |
//|  4. 顺序访问：仅支持线性遍历（无索引随机访问），查找效率 O(n)；     |
//| 适用场景：所有需要频繁在列表中间插入/删除元素，且无需随机访问的场景，如： |
//|  - 任务队列（按优先级在队列中间插入任务，如高优先级任务插队）；      |
//|  - 历史操作记录（仅需按顺序遍历，频繁在头部添加最新记录）；          |
//|  - 双向链表结构的业务数据（如订单依赖链、节点关系图）；              |
//|  - 大数据量下的中间插入场景（相比数组 O(n) 移动元素，链表 O(1) 操作） |
//+------------------------------------------------------------------+
template<typename T>
class CLinkedList : public ICollection<T>
  {
protected:
   CLinkedListNode<T>* m_head;       // 链表头节点指针（循环链表的入口，指向第一个节点）
   int               m_count;        // 当前链表中的节点数量（≥0，空链表为0）

public:
   //----------------------------------------------------------------
   // 构造与析构接口
   //----------------------------------------------------------------
   /**
    * @brief 默认构造函数：创建空的双向循环链表
    * @note 初始状态：头节点 m_head 为 NULL，节点数量 m_count 为0
    */
                     CLinkedList(void);

   /**
    * @brief 从集合构造：创建链表并复制指定集合的所有元素（按集合顺序添加到链表尾部）
    * @param collection [in] 源集合（实现 ICollection<T> 接口，如 ArrayList/HashSet）
    * @note 元素添加顺序与源集合一致，每个元素对应一个链表节点
    */
                     CLinkedList(ICollection<T>* collection);

   /**
    * @brief 从数组构造：创建链表并复制指定数组的所有元素（按数组顺序添加到链表尾部）
    * @param array [in] 源数组（元素类型与 T 一致）
    * @note 元素添加顺序与数组索引顺序一致（array[0] 为链表第一个节点，array[n] 为最后一个）
    */
                     CLinkedList(T &array[]);

   /**
    * @brief 析构函数：清空链表并释放所有节点内存
    * @note 内部调用 Clear() 方法，删除所有节点，避免内存泄漏
    */
                    ~CLinkedList(void);

   //----------------------------------------------------------------
   // 元素添加接口（支持多种插入位置）
   //----------------------------------------------------------------
   /**
    * @brief 在链表尾部添加元素（等价于 AddLast(value)）
    * @param value [in] 待添加的元素值
    * @return bool - 添加结果：true=添加成功（节点创建并插入成功）；false=添加失败（内存不足等）
    * @note 继承自 ICollection<T> 接口的基础添加方法
    */
   bool              Add(T value);

   /**
    * @brief 在指定节点之后插入新元素（创建新节点并关联到链表）
    * @param node [in] 目标节点（需属于当前链表，否则返回 NULL）
    * @param value [in] 待插入的元素值
    * @return CLinkedListNode<T>* - 新创建的节点指针（成功）；NULL（失败，如节点无效）
    * @note 操作效率 O(1)，无需移动其他节点，仅修改前后节点指针
    */
   CLinkedListNode<T>* AddAfter(CLinkedListNode<T>* node, T value);

   /**
    * @brief 在指定节点之后插入已存在的节点（将外部节点关联到当前链表）
    * @param node [in] 目标节点（需属于当前链表，否则返回 false）
    * @param new_node [in] 待插入的外部节点（需未关联其他链表，否则返回 false）
    * @return bool - 插入结果：true=插入成功；false=插入失败（节点无效或已关联其他链表）
    * @note 适用于节点复用场景，避免重复创建节点（如将节点从一个链表迁移到另一个）
    */
   bool              AddAfter(CLinkedListNode<T>* node, CLinkedListNode<T>* new_node);

   /**
    * @brief 在指定节点之前插入新元素（创建新节点并关联到链表）
    * @param node [in] 目标节点（需属于当前链表，否则返回 NULL）
    * @param value [in] 待插入的元素值
    * @return CLinkedListNode<T>* - 新创建的节点指针（成功）；NULL（失败，如节点无效）
    * @note 若目标节点是头节点，新节点将成为新的头节点（m_head 指向新节点）
    */
   CLinkedListNode<T>* AddBefore(CLinkedListNode<T>* node, T value);

   /**
    * @brief 在指定节点之前插入已存在的节点（将外部节点关联到当前链表）
    * @param node [in] 目标节点（需属于当前链表，否则返回 false）
    * @param new_node [in] 待插入的外部节点（需未关联其他链表，否则返回 false）
    * @return bool - 插入结果：true=插入成功；false=插入失败（节点无效或已关联其他链表）
    * @note 若目标节点是头节点，新节点将成为新的头节点
    */
   bool              AddBefore(CLinkedListNode<T>* node, CLinkedListNode<T>* new_node);

   /**
    * @brief 在链表头部插入新元素（创建新节点并设为头节点）
    * @param value [in] 待插入的元素值
    * @return CLinkedListNode<T>* - 新创建的头节点指针（成功）；NULL（失败）
    * @note 操作效率 O(1)，新节点的 next 指向原头节点，原头节点的 prev 指向新节点
    */
   CLinkedListNode<T>* AddFirst(T value);

   /**
    * @brief 在链表头部插入已存在的节点（将外部节点设为头节点）
    * @param node [in] 待插入的外部节点（需未关联其他链表，否则返回 false）
    * @return bool - 插入结果：true=插入成功（节点成为新头节点）；false=插入失败
    */
   bool              AddFirst(CLinkedListNode<T>* node);

   /**
    * @brief 在链表尾部插入新元素（创建新节点并设为尾节点）
    * @param value [in] 待插入的元素值
    * @return CLinkedListNode<T>* - 新创建的尾节点指针（成功）；NULL（失败）
    * @note 操作效率 O(1)，新节点的 prev 指向原尾节点，原尾节点的 next 指向新节点
    */
   CLinkedListNode<T>* AddLast(T value);

   /**
    * @brief 在链表尾部插入已存在的节点（将外部节点设为尾节点）
    * @param node [in] 待插入的外部节点（需未关联其他链表，否则返回 false）
    * @return bool - 插入结果：true=插入成功（节点成为新尾节点）；false=插入失败
    */
   bool              AddLast(CLinkedListNode<T>* node);

   //----------------------------------------------------------------
   // 基础信息与包含性检查接口
   //----------------------------------------------------------------
   /**
    * @brief 获取链表中的节点数量（元素总数）
    * @return int - 节点数量（≥0，空链表返回0）
    */
   int               Count(void);

   /**
    * @brief 获取链表的头节点指针（直接暴露头节点，用于遍历或节点操作）
    * @return CLinkedListNode<T>* - 头节点指针（空链表返回 NULL）
    * @note 遍历链表时，从 head 开始，通过 Next() 依次访问节点，直到回到 head
    */
   CLinkedListNode<T>* Head(void) { return(m_head); }

   /**
    * @brief 获取链表的第一个节点（与 Head() 功能一致，为兼容接口命名）
    * @return CLinkedListNode<T>* - 第一个节点指针（空链表返回 NULL）
    */
   CLinkedListNode<T>* First(void);

   /**
    * @brief 获取链表的最后一个节点
    * @return CLinkedListNode<T>* - 最后一个节点指针（空链表返回 NULL）
    * @note 内部通过头节点的 Previous() 获取（循环链表特性：head->prev 是尾节点）
    */
   CLinkedListNode<T>* Last(void);

   /**
    * @brief 检查链表是否包含指定元素
    * @param item [in] 待检查的元素值（类型与 T 一致）
    * @return bool - 检查结果：true=包含该元素；false=不包含
    * @note 内部调用 Find(item) 实现，线性遍历链表，时间复杂度 O(n)
    */
   bool              Contains(T item);

   //----------------------------------------------------------------
   // 批量复制接口
   //----------------------------------------------------------------
   /**
    * @brief 将链表中的所有元素按顺序复制到外部数组
    * @param dst_array [out] 目标数组（需提前分配空间，或由方法自动扩容）
    * @param dst_start [in] 目标数组的起始复制索引（默认从0开始）
    * @return int - 实际复制的元素数量（等于 Count()，空链表返回0）
    * @note 复制顺序与链表遍历顺序一致（从 First() 到 Last()）
    */
   int               CopyTo(T &dst_array[], const int dst_start=0);

   //----------------------------------------------------------------
   // 清理与删除接口
   //----------------------------------------------------------------
   /**
    * @brief 清空链表：删除所有节点，释放内存，重置链表状态
    * @note 清空后：头节点 m_head 为 NULL，节点数量 m_count 为0，所有节点内存被释放
    */
   void              Clear(void);

   /**
    * @brief 从链表中删除首次出现的指定元素（删除对应的节点）
    * @param item [in] 待删除的元素值（类型与 T 一致）
    * @return bool - 删除结果：true=删除成功（找到元素并删除节点）；false=删除失败（元素不存在）
    * @note 内部逻辑：先调用 Find(item) 找到节点，再调用 InternalRemoveNode() 删除
    */
   bool              Remove(T item);

   /**
    * @brief 从链表中删除指定节点（直接操作节点，效率更高）
    * @param node [in] 待删除的节点（需属于当前链表，否则返回 false）
    * @return bool - 删除结果：true=删除成功；false=删除失败（节点无效或不属于当前链表）
    * @note 操作效率 O(1)，仅修改前后节点指针，无需移动其他节点
    */
   bool              Remove(CLinkedListNode<T>* node);

   /**
    * @brief 删除链表的头节点（第一个元素）
    * @return bool - 删除结果：true=删除成功（链表非空）；false=删除失败（链表为空）
    * @note 操作效率 O(1)，删除后原头节点的 Next() 成为新头节点
    */
   bool              RemoveFirst(void);

   /**
    * @brief 删除链表的尾节点（最后一个元素）
    * @return bool - 删除结果：true=删除成功（链表非空）；false=删除失败（链表为空）
    * @note 操作效率 O(1)，内部通过头节点的 Previous() 获取尾节点，再删除
    */
   bool              RemoveLast(void);

   //----------------------------------------------------------------
   // 节点查找接口
   //----------------------------------------------------------------
   /**
    * @brief 查找链表中首次出现指定元素的节点（从头部开始遍历）
    * @param value [in] 待查找的元素值（类型与 T 一致）
    * @return CLinkedListNode<T>* - 查找结果：找到返回节点指针；未找到返回 NULL
    * @note 遍历顺序：从 First() 到 Last()，时间复杂度 O(n)
    */
   CLinkedListNode<T>* Find(T value);

   /**
    * @brief 查找链表中最后一次出现指定元素的节点（从尾部开始遍历）
    * @param value [in] 待查找的元素值（类型与 T 一致）
    * @return CLinkedListNode<T>* - 查找结果：找到返回节点指针；未找到返回 NULL
    * @note 遍历顺序：从 Last() 到 First()，时间复杂度 O(n)
    */
   CLinkedListNode<T>* FindLast(T value);

private:
   //----------------------------------------------------------------
   // 内部辅助接口（不对外暴露，仅用于实现核心逻辑）
   //----------------------------------------------------------------
   /**
    * @brief 验证节点是否有效（非空且属于当前链表）
    * @param node [in] 待验证的节点指针
    * @return bool - 验证结果：true=节点有效；false=节点无效（空指针或属于其他链表）
    */
   bool              ValidateNode(CLinkedListNode<T>* node);

   /**
    * @brief 验证新节点是否可插入（非空且未关联任何链表）
    * @param node [in] 待验证的外部节点指针
    * @return bool - 验证结果：true=节点可插入；false=节点不可插入（空指针或已关联链表）
    */
   bool              ValidateNewNode(CLinkedListNode<T>* node);

   /**
    * @brief 在指定节点之前插入新节点（内部通用插入逻辑，处理指针关联）
    * @param node [in] 目标节点（插入位置在该节点之前）
    * @param new_node [in] 待插入的新节点（已验证有效）
    * @note 仅修改前后节点的 next/prev 指针，不处理链表头节点更新（由上层方法处理）
    */
   void              InternalInsertNodeBefore(CLinkedListNode<T>* node, CLinkedListNode<T>* new_node);

   /**
    * @brief 向空链表插入第一个节点（初始化链表循环结构）
    * @param new_node [in] 待插入的节点（将成为链表唯一节点）
    * @note 设置节点的 next 和 prev 指向自身（循环链表特性），并更新头节点 m_head
    */
   void              InternalInsertNodeToEmptyList(CLinkedListNode<T>* new_node);

   /**
    * @brief 从链表中删除指定节点（内部通用删除逻辑，处理指针关联与内存释放）
    * @param node [in] 待删除的节点（已验证有效）
    * @note 处理链表为空、删除头节点等特殊场景，删除后释放节点内存
    */
   void              InternalRemoveNode(CLinkedListNode<T>* node);
  };
//+------------------------------------------------------------------+